package cxydmmszl.chapter02.t029;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;

/**
 * <li style="color: red;">Prob</li>
 * 向有序的环形链表中插入新节点
 * <li style="color: green;">Desc</li>
 * 一个环形单链表从头节点 head 开始不降序，同时由最后的节点指回头节点。
 * 给定这样一个环形单链表的头节点 head 和一个整数 num， 请生成节点值为 num 的新节点，
 * 并插入到这个环形链表中，保证调整后的链表依然有序。
 * <li style="color: green;">Input</li>
 * 环形单链表的头节点 head 和 一个整数 num。
 * <li style="color: green;">Output</li>
 * 在给定的函数内返回新的环形单链表的头指针。
 * <li style="color: blue;">Link</li> CD158
 *
 * @author habitplus
 * @since 2021-09-11 15:41
 */
public class Main {
    private static final StreamTokenizer st =
            new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    private static int nextInt() {
        try {
            st.nextToken();
            return (int) st.nval;
        } catch (IOException e) {
            e.printStackTrace();
        }
        return 0;
    }

    private static class Node {
        int val;
        Node next;
        public Node(int val) {
            this.val = val;
        }
    }

    private static Node readAndGenCycleList(int n) {
        Node tou = new Node(0), pre = tou, node;
        int num;
        for (int i = 0; i < n; i++) {
            num = nextInt();
            node = new Node(num);
            pre.next = node;
            pre = node;
        }
        if (pre.next != tou) pre.next = tou.next;
        return tou.next;
    }

    private static void printCycleLinkedList(Node head) {
        if (head == null) {
            System.out.println();
        }

        StringBuilder sb = new StringBuilder();
        Node pre = head;
        Node cur = head.next;
        while (cur != head) {
            sb.append(pre.val).append(" ");
            pre = cur;
            cur = cur.next;
        }

        sb.append(pre.val).append(" ");
        System.out.println(sb.toString());
    }

    private static Node insertNum(Node head, int num) {
        Node node = new Node(num);
        if (head == null) {
            node.next = node;
            return node;
        }

        Node pre = head;
        Node cur = head.next;
        while (cur != head) {
            if (pre.val <= num && cur.val >= num) {
                break;
            }
            pre = cur;
            cur = cur.next;
        }

        pre.next = node;
        node.next = cur;
        return head.val < num ? head : node;
    }

    public static void main(String[] args) {
        int n = nextInt();
        Node h = readAndGenCycleList(n);
        int num = nextInt();

        h = insertNum(h, num);
        printCycleLinkedList(h);
    }
}
